Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Root to Leaf Path Pattern (medium)
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Leaf Processing Pattern (medium)
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Tree View Pattern (medium)
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Comparison of Two Trees Pattern (medium)
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Isomorphic Trees

Problem Statement

Given root of two binary trees root1 and root2, return true if they are isomorphic. Otherwise, return false.

Two trees are said to be isomorphic if one tree can be transformed into the other by swapping the left and right children of some nodes.

Note that the structure should be identical after possible swaps, and the values of nodes must be the same in both trees.

Examples

Example 1

  • Input: root1 = [1, 2, 3, 4], root2 = [1, 3, 2, null, null, 4]
Image
  • Output: true
  • Explanation: In the first tree, we can swap 2 with 3, and 4 with null to get the second tree by swapping.

Example 2

  • Input: root1 = [1, 2, 3], root2 = [1, 3, 2]
Image
  • Output: true
  • Explanation: We can swap the left and right children of the root node in Tree 1. This transforms Tree 1 into Tree 2.

Example 3

  • Input: root1 = [1, 2, 3, 4, 5, 6, 7], root2 = [1, 4, 3, 2, 5, 7, 6]
Image
  • Output: false
  • Explanation: We can't get tree2 by performing swap operations in tree1.

Solution

To solve this problem, we will use Depth-First Search (DFS) to compare both trees node by node. The key is to check if the current nodes in both trees match and then recursively verify their children. If they can be swapped and still match, the trees are isomorphic. Our approach focuses on exploring both possibilities: when the left children match with the left children, and when the left children match with the right children (after a swap). This approach is effective as it directly handles the recursive nature of trees and the swap condition, ensuring that we cover all potential transformations.

DFS ensures that we explore all nodes and their children thoroughly. This is important because both the structure and values of the trees must match after considering possible swaps at each node.

Step-by-Step Algorithm

  1. Base Case 1:

    • Check if both root1 and root2 are null.
    • If both trees are empty, return true because two empty trees are considered isomorphic.
  2. Base Case 2:

    • Check if either root1 or root2 is null.
    • If one tree is empty and the other is not, return false because one tree being non-existent makes them non-isomorphic.
  3. Compare Node Values:

    • Compare the values of the current nodes (root1.val and root2.val).
    • If their values do not match, return false because nodes with different values cannot be considered isomorphic.
  4. Recursive Check without Swap:

    • Check if the left child of root1 is isomorphic to the left child of root2 and the right child of root1 is isomorphic to the right child of root2.
    • This is the scenario where no swapping occurs. Call the isIsomorphic() function recursively for both left and right subtrees.
  5. Recursive Check with Swap:

    • Check if the left child of root1 is isomorphic to the right child of root2 and the right child of root1 is isomorphic to the left child of root2.
    • This is the scenario where swapping occurs. Call the isIsomorphic() function recursively with swapped children.
  6. Final Check:

    • If either of the checks (with or without swap) returns true, then the trees are isomorphic. Return true.
    • If both checks return false, then the trees are not isomorphic. Return false.

Algorithm Walkthrough

Example Input:

  • root1 = [1, 2, 3, 4]
  • root2 = [1, 3, 2, null, null, null, 4]
  1. Step 1: Start by comparing the root nodes of both trees:

    • root1.val = 1
    • root2.val = 1
    • Since the values are equal, we proceed to check the children.
  2. Step 2: First, we try comparing the children without any swaps:

    • Compare root1.left (value 2) with root2.left (value 3).
      • Check 1: 2 != 3, so the comparison without swaps fails.
    • Compare root1.right (value 3) with root2.right (value 2).
      • Check 2: 3 != 2, so the comparison without swaps fails completely.
  3. Step 3: Since comparing without swaps failed, we now try comparing the trees with a swap:

    • Compare root1.left (value 2) with root2.right (value 2).
      • Check 3: 2 == 2, so the values match. Now, we need to compare their respective children.
  4. Step 4: Now, compare the subtrees of root1.left and root2.right. Start by comparing without swap for this subtree:

    • Compare root1.left.left (value 4) with root2.right.left (null).
      • Check 4: 4 != null, so the comparison without swap for this subtree fails.
  5. Step 5: Since the comparison without swap for the subtree failed, we now swap the children and try again:

    • Compare root1.left.left (value 4) with root2.right.right (value 4).
      • Check 5: 4 == 4, so the values match. Now, compare their children.
        • Both root1.left.left.left and root2.right.right.left are null.
        • Both root1.left.left.right and root2.right.right.right are null.
      • Since both children are null, this subtree returns true.
  6. Step 6: Next, compare the right child of root1.left and left child of root2.right:

    • Both root1.left.right and root2.right.left are null.
    • Check 6: Since both children are null, this subtree returns true.
  7. Step 7: Since the left and right subtrees of root1.left and root2.right match after the swap, the recursive check with swap for this subtree returns true.

  8. Step 8: Now, compare the right child of root1 and left child of root2:

    • Compare root1.right (value 3) with root2.left (value 3).
    • Check 7: 3 == 3, so the values match. Now, compare their children.
      • Both root1.right.left and root2.left.left are null.
      • Both root1.right.right and root2.left.right are null.
    • Check 8: Since both children are null, this subtree returns true.
  9. Final Step: Since the recursive check with swap for the left children and the comparison of the right children return true, the final result is:

    • The two trees are isomorphic, so the function returns true.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • Each node of both trees is visited once. At each node, we perform a constant amount of work (comparisons and recursive calls).
  • Therefore, the time complexity of the solution is , where N1 and N2 are the number of nodes in root1 and root2 respectively.
  • This is because we are traversing both trees simultaneously, and the traversal will stop once we reach the end of the smaller tree.

Space Complexity

  • The space complexity is determined by the depth of the recursion stack.
  • In the worst case (for highly unbalanced trees), the depth of recursion could be the height of the tree, leading to space complexity, where H1 and H2 are the heights of root1 and root2, respectively.
  • For balanced trees, the height is logarithmic, so the space complexity is in the best case.
Isomorphic Trees (medium)
Introduction to Serialize and Deserialize Tree Pattern
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity